/* 653. 两数之和 IV - 输入 BST */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */

/* 深度优先搜索 递归 */
var findTarget = function (root, k) {
    const set = new Set()
    const dfs = (root, k) => {
        if (!root) return false
        if (set.has(k - root.val)) return true
        set.add(k - root)
        return dfs(root.left, k) || dfs(root.right, k)
    }
    return dfs(root, k)
};

/* 广度优先搜素 迭代 */
var findTarget = function (root, k) {
    const set = new Set()
    const queue = [root]
    while (queue.length) {
        const node = queue.shift()
        if (set.has(k - root.val)) return true
        set.add(root.val)
        if (node.left) {
            queue.push(node.left)
        }
        if (node.right) {
            queue.push(node.right)
        }
    }
    return false
}

/* 深度优先搜索 + 中序遍历 + 双指针 */
var findTarget = function (root, k) {
    const list = []
    const inorderTraversal = node => {
        if (!node) return
        inorderTraversal(node.left)
        list.push(node.val)
        inorderTraversal(node.right)
    }
    inorderTraversal(root)
    let left = 0, right = list.length - 1

    while (left < right) {
        if (list[left] + list[right] === k) {
            return true
        }
        if (list[left] + list[right] < k) {
            left++
        } else {
            right--
        }
    }
    return false
}

/* 迭代 + 中序遍历 + 双指针  */
var findTarget = function (root, k) {
    const getLeft = stack => {
        const root = stack.pop()
        let node = root.right
        while (node) {
            stack.push(node)
            node = node.left
        }
        return root
    }

    const getRight = (stack) => {
        const root = stack.pop()
        let node = root.left
        while (node) {
            stack.push(node)
            node = node.right
        }
        return root
    }

    let left = root, right = root
    const leftStack = [left], rightStack = [right]

    while (left.left) {
        leftStack.push(left.left)
        left = left.left
    }
    while (right.right) {
        rightStack.push(right.right)
        right = right.right
    }
    while (left !== right) {
        if (left.val + right.val === k) return true
        if (left.val + right.val < k) {
            left = getLeft(leftStack)
        } else {
            right = getRight(rightStack)
        }
    }

    return false

}